#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 全排列
// 子集
// 电话号码的组合
// 组合总和
// 括号生成
// 单词搜索
// 分割回文串
// N皇后
// 不同路径III
// 组合
// 编辑距离
// 组合总和II

// 全排列
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    bool check[7];
    vector<vector<int>> permute(vector<int> &nums)
    {
        dfs(nums);
        return ans;
    }
    void dfs(vector<int> &nums)
    {
        if (path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

// 子集
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> subsets(vector<int> &nums)
    {
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int> &nums, int pos)
    {
        ans.push_back(path);
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};

// 电话号码的组合
class Solution
{
public:
    string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans;
    string path;
    vector<string> letterCombinations(string digits)
    {
        if (digits == "")
            return {};
        dfs(digits, 0);
        return ans;
    }

    void dfs(string digits, int pos)
    {
        if (pos == digits.size())
        {
            ans.push_back(path);
            return;
        }
        for (auto ch : hash[digits[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

// 组合总和
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    int aim;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        aim = target;
        dfs(candidates, 0, 0);
        return ans;
    }

    void dfs(vector<int> &nums, int sum, int pos)
    {
        if (sum == aim)
        {
            ans.push_back(path);
            return;
        }
        else if (sum > aim)
            return;

        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, sum + nums[i], i);
            path.pop_back();
        }
    }
};

// 括号生成
class Solution
{
public:
    vector<string> ans;
    string path;
    int left, right, n;
    // 有效括号:1.左括号的数量 == 右括号的数量
    // 2.在任意一个字符串中左括号的数量 >= 右括号的数量
    vector<string> generateParenthesis(int _n)
    {
        n = _n;
        dfs();
        return ans;
    }

    void dfs()
    {
        // 因为是后添加右括号,所以右括号等于n的时候返回加入到结果中
        if (right == n)
        {
            ans.push_back(path);
            return;
        }
        // 左括号符合条件加添加左括号
        if (left < n)
        {
            path += '(';
            left++;
            dfs();
            path.pop_back();
            left--;
        }
        // 右括号符合条件加添加右括号
        if (right < left)
        {
            path += ')';
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }
};

// 单词搜索
class Solution
{
public:
    int m, n;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[7][7];
    bool exist(vector<vector<char>> &board, string word)
    {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if (dfs(board, i, j, word, 1))
                        return true;
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &board, int i, int j, string word, int pos)
    {
        if (pos == word.size())
        {
            return true;
        }

        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos])
            {
                vis[x][y] = true;
                // 如果下一层返回为true，则不需要继续下一个方位进行选择
                // 否则继续下一个方位
                if (dfs(board, x, y, word, pos + 1))
                    return true;
                vis[x][y] = false;
            }
        }

        return false;
    }
};

// 分割回文串
class Solution
{
public:
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<bool>> dp;
    int n;
    vector<vector<string>> partition(string s)
    {
        n = s.size();
        dp.assign(n, vector<bool>(n, true));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < n; j++)
            {
                dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ans;
    }

    void dfs(string s, int pos)
    {
        if (pos == n)
        {
            ans.push_back(path);
            return;
        }

        for (int i = pos; i < n; i++)
        {
            if (dp[pos][i])
            {
                path.push_back(s.substr(pos, i - pos + 1));
                dfs(s, i + 1);
                path.pop_back();
            }
        }
    }
};

// N皇后
class Solution
{
public:
    bool CheckCol[10];  // 列
    bool CheckDig1[20]; // 正对角线
    bool CheckDig2[20]; // 反对角线
    vector<vector<string>> ans;
    vector<string> path;
    int n;
    vector<vector<string>> solveNQueens(int _n)
    {
        n = _n;
        path.resize(n);
        for (int i = 0; i < n; i++)
        {
            path[i].append(n, '.');
        }

        dfs(0);
        return ans;
    }

    void dfs(int row)
    {
        if (row == n)
        {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < n; i++)
        {
            // 正对角线 y = x + b  y - x + n = b + n
            // 反对角线 y = -x + b  y + x = b
            if (!CheckCol[i] && !CheckDig1[row - i + n] && !CheckDig2[row + i])
            {
                CheckCol[i] = CheckDig1[row - i + n] = CheckDig2[row + i] = true;
                path[row][i] = 'Q';
                dfs(row + 1);
                CheckCol[i] = CheckDig1[row - i + n] = CheckDig2[row + i] = false;
                path[row][i] = '.';
            }
        }
    }
};

// 不同路径III
class Solution
{
public:
    bool vis[21][21];
    int ans, step;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
    int uniquePathsIII(vector<vector<int>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        // 记录起始下标
        int bx = 0, by = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 0)
                    step++;
                else if (grid[i][j] == 1)
                {
                    bx = i;
                    by = j;
                }
            }
        }

        // step加上起始和结束位置
        step += 2;
        vis[bx][by] = true;
        dfs(grid, bx, by, 1);
        return ans;
    }

    void dfs(vector<vector<int>> &grid, int i, int j, int count)
    {
        if (grid[i][j] == 2)
        {
            if (count == step)
                ans++;
            return;
        }

        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1)
            {
                vis[x][y] = true;
                dfs(grid, x, y, count + 1);
                vis[x][y] = false;
            }
        }
    }
};

// 组合
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> combine(int n, int k)
    {
        dfs(1, n, k);
        return ans;
    }

    void dfs(int pos, int n, int k)
    {
        if (path.size() == k)
        {
            ans.push_back(path);
            return;
        }

        for (int i = pos; i <= n; i++)
        {
            path.push_back(i);
            dfs(i + 1, n, k);
            path.pop_back();
        }
    }
};

// 编辑距离
class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        // dp[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; i++)
            dp[i][0] = i;
        for (int j = 0; j <= n; j++)
            dp[0][j] = j;

        word1 = ' ' + word1;
        word2 = ' ' + word2;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (word1[i] == word2[j])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
            }
        }

        return dp[m][n];
    }
};

// 组合总和
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    int aim;
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        aim = target;
        dfs(candidates, 0, 0);

        return ans;
    }

    void dfs(vector<int> &candidates, int sum, int pos)
    {
        if (sum > aim)
            return;
        if (sum == aim)
        {
            ans.push_back(path);
            return;
        }

        // 当前层数字不能重复
        unordered_set<int> hash;
        for (int i = pos; i < candidates.size(); i++)
        {
            if (hash.count(candidates[i]))
                continue;
            hash.insert(candidates[i]);
            path.push_back(candidates[i]);
            dfs(candidates, sum + candidates[i], i + 1);
            path.pop_back();
        }
    }
};